package com.itheima.datastructure.binarytree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import static com.itheima.datastructure.binarytree.E01Leetcode144.colorPrintln;

/**
 * 二叉树后序遍历(左,右,值)--后续遍历
 */
public class E03Leetcode145 {

    /**
     * 后续遍历
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        //记录路径
        LinkedList<TreeNode> stack = new LinkedList<>();

        TreeNode curr = root; // 代表当前节点
        TreeNode pop = null; // 最近一次弹栈的元素

        List<Integer> result = new ArrayList<>();
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                // 待处理左子树
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                // 没有右子树
                if (peek.right == null) {
                    pop = stack.pop();
                    result.add(pop.val);

                }
                // 右子树处理完成（表示是从右子树处理完成往回走）
                else if (peek.right == pop) {
                    pop = stack.pop();
                    result.add(pop.val);
                }
                // 待处理右子树
                else {
                    curr = peek.right;
                }
            }
        }
        return result;
    }

    public static void print(TreeNode root) {
        //记录路径
        LinkedList<TreeNode> stack = new LinkedList<>();

        TreeNode curr = root; // 代表当前节点
        TreeNode pop = null; // 最近一次弹栈的元素

        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                colorPrintln("前序: " + curr.val, 31);
                // 待处理左子树
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                // 没有右子树
                if (peek.right == null) {
                    pop = stack.pop();

                    colorPrintln("后续: " + pop.val, 34);
                    colorPrintln("中序: " + pop.val, 36);
                }
                // 右子树处理完成（表示是从右子树处理完成往回走）
                else if (peek.right == pop) {
                    pop = stack.pop();

                    colorPrintln("后续: " + pop.val, 34);
                }
                // 待处理右子树
                else {
                    colorPrintln("中序: " + peek.val, 36);
                    curr = peek.right;
                }
            }
        }
    }

    //二叉树：
    //     1
    //    /   \
    //   2     3
    //  / \   / \
    // 4   5 6   7
    //前序：1,2,4,5,3,6,7
    //中序：4,2,5,1,6,3,7
    //后序：4,5,2,6,7,3,1
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(new TreeNode(4), 2, new TreeNode(5)),
                1,
                new TreeNode(new TreeNode(6), 3, new TreeNode(7))
        );
//        print(root);
        List[] lists = orderTraversal(root);
        System.out.println("前序:" + lists[0]); //1,2,4,5,3,6,7
        System.out.println("中序:" + lists[1]); //4,2,5,1,6,3,7
        System.out.println("后序:" + lists[2]); //4,5,2,6,7,3,1

    }


    //二叉树：
    //     1
    //    /   \
    //   2     3
    //  / \   / \
    // 4   5 6   7
    public static List[] orderTraversal(TreeNode root) {
        //前序结果 打印当前节点-访问左子树-访问右子树
        List<Integer> preOrder = new ArrayList<>();
        //中序结果 访问左子树-打印当前节点-访问右子树
        List<Integer> inOrder = new ArrayList<>();
        //后序结果 访问左子树-访问右子树-打印当前节点
        List<Integer> postOrder = new ArrayList<>();

        TreeNode curr = root;
        TreeNode pop = null; // 最近一次弹栈的元素
        LinkedList<TreeNode> stack = new LinkedList<>();

        while (null != curr || !stack.isEmpty()) {

            if (null != curr) { //去的路~
                colorPrintln("去>: " + curr.val, 31); //1,2,4,5,3,6,7
                printStep(List.of(
                        "前序(打印当前-访问左子树-访问右子树)：完成【】->打印当前 ->访问左子树",
                        "中序(访问左子树-打印当前-访问右子树)：完成【】->访问左子树",
                        "后序(访问左子树-访问右子树-打印当前)：完成【】->访问左子树"
                ));
                //前序： 打印当前节点
                preOrder.add(curr.val);
                //记录路径
                stack.push(curr);
                //访问左子树
                curr = curr.left;
            } else {
                //回去的路~
                TreeNode peek = stack.peek();
                colorPrintln("回<: " + peek.val, 36); // 4,2,5,2,1,6,3,7,3,1
                if (peek.right == null) {
                    System.out.println("没有右子树....." + peek.val);
                    printStep(Arrays.asList(
                            "前序(打印当前-访问左子树-访问右子树)：完成【打印当前->访问左子树】->访问右子树null",
                            "中序(访问左子树-打印当前-访问右子树)：完成【访问左子树】->打印当前->访问右子树null",
                            "后序(访问左子树-访问右子树-打印当前)：完成【访问左子树】->访问右子树null ->打印当前"));
                    pop = stack.pop();
                    inOrder.add(pop.val);
                    postOrder.add(pop.val);
                } else {
                    if (peek.right == pop) {//说明当前弹栈的节点的右节点== 上一次弹栈的节点，说明是从右子树处理完成往回走
                        System.out.println("[有右子树]从右子树处理完成往回走....." + peek.val);

                        printStep(Arrays.asList(
                                "前序(打印当前-访问左子树-访问右子树)：完成【打印当前 ->访问左子树 ->访问右子树】",
                                "中序(访问左子树-打印当前-访问右子树)：完成【访问左子树 ->打印当前 ->访问右子树】",
                                "后序(访问左子树-访问右子树-打印当前)：完成【访问左子树 ->访问右子树】->打印当前节点"));
                        pop = stack.pop();
                        postOrder.add(pop.val);
                    } else { // 从左子树处理完成往回走，再访问右子树
                        System.out.println("[有右子树]从左子树处理完成往回走....." + peek.val);
                        printStep(Arrays.asList(
                                "前序(打印当前-访问左子树-访问右子树)：完成【打印当前 ->访问左子树】->访问右子树",
                                "中序(访问左子树-打印当前-访问右子树)：完成【访问左子树】->打印当前 ->访问右子树",
                                "后序(访问左子树-访问右子树-打印当前)：完成【访问左子树】->访问右子树"));
                        inOrder.add(peek.val);
                        curr = peek.right;
                    }
                }
            }
        }
        return new List[]{preOrder, inOrder, postOrder};
    }

    private static void printStep(List<String> steps) {
        int maxLen = 0;
        for (String step : steps) {
            if (step.length() > maxLen) {
                maxLen = step.length();
            }
        }
        String line = "|" + "--".repeat(maxLen) + "|";
        System.out.println(line);
        for (String step : steps) {
            System.out.print("     " + step  + "\n");
        }
        System.out.println(line);


    }
}
